package sword.chapter6Stack;

import java.util.Stack;

/**
 * 矩阵中最大的矩形
 * 与39直方图最大矩形面积类似，需要将矩阵转为直方图，进而求最大矩形面积
 * <p>
 * 矩阵转为直方图，只要当前元素为0，就需要将heights[i]初始为0，否则++
 *
 * @author K
 * @date 2021-12-05 14:38
 */
public class S40MaximalRectangle {
    public static int s40(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for (int[] row : matrix) {
            for (int i = 0; i < row.length; i++) {
                if (row[i] == 0) {
                    heights[i] = 0;
                } else {
                    heights[i]++;
                }
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                int height = heights[stack.pop()];
                int prevShortIndex = stack.peek();
                int width = i - prevShortIndex - 1;
                int tempArea = height * width;
                maxArea = Math.max(maxArea, tempArea);
            }
            stack.push(i);
        }

        while (stack.peek() != -1) {
            int height = heights[stack.pop()];
            int prevShortIndex = stack.peek();
            int width = heights.length - prevShortIndex - 1;
            int tempArea = height * width;
            maxArea = Math.max(maxArea, tempArea);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[][] ints = new int[4][5];
        ints[0] = new int[]{1, 0, 1, 0, 0};
        ints[1] = new int[]{0, 0, 1, 1, 1};
        ints[2] = new int[]{1, 1, 1, 1, 1};
        ints[3] = new int[]{1, 0, 0, 1, 0};
        int result = s40(ints);
        System.out.println();
    }
}
